<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i < str.length; i++) {
                        // 34 43 43 都是常用的底数
                        hashCode = 37 * hashCode + str.charCodeAt(i);
                    }
                    return hashCode % size;
                };
                // 插入和修改方法
                HashTable.prototype.put = function (key, value) {
                    // 根据key获取对应的index
                    var index = this.hashFunction(key, this.limit);
                    // 根据index取出对应的bucket
                    var bucket = this.storage[index];
                    if (bucket == null) {
                        bucket = [];
                        this.storage[index] = bucket;
                    }
                    // 判断是否是修改数据
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            tuple[1] == value;
                            return;
                        }
                    }
                    // 不是修改数据就添加数据
                    bucket.push([key, value]);
                    this.count++;
                    // 扩容
                    if (this.count > this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            value == tuple[1];
                            return value;
                        }
                    }
                    return null;
                };
                // 删除
                HashTable.prototype.remove = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            // 从i开始删除一个
                            bucket.splice(i, 1);
                            this.count--;
                            // 缩容
                            if (this.limit > 7 && this.count < this.limit * 0.25) {
                                var newLimit = Math.floor(this.limit / 2);
                                var prime = this.getPrime(newLimit);
                                this.resize(prime);
                            }
                            return tuple[1];
                        }
                    }
                    return null;
                };
                // 扩容
                HashTable.prototype.resize = function (newLimit) {
                    var oldStorage = this.storage;
                    // 充值所有的属性
                    this.storage = [];
                    this.count = 0;
                    this.limit = newLimit;
                    for (var i = 0; i < this.limit; i++) {
                        var bucket = oldStorage[i];
                        if (bucket == null) {
                            continue;
                        }
                        for (var j = 0; j < bucket.length; j++) {
                            var tuple = bucket[j];
                            this.put(tuple[0], tuple[1]);
                        }
                    }
                };
                // 为空？
                HashTable.prototype.isEmpty = function () {
                    return this.count > 0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i < this.limit; i++) {
                        var arr = this.storage[i];

                        if (arr != undefined) {
                            str += '[';
                            for (var j = 0; j < arr.length; j++) {
                                var bucket = arr[j];

                                str += '[' + bucket[0] + ',' + bucket[1] + ']';
                                if (j != arr.length - 1) {
                                    str += ',';
                                }
                            }
                            str += ']';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        } else {
                            str += '[]';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        }
                    }

                    return str;
                };
                HashTable.prototype.isPrime = function (num) {
                    if (num <= 1) {
                        return false;
                    }
                    //1.获取num的平方根:Math.sqrt(num)
                    //2.循环判断
                    for (var i = 2; i <= Math.sqrt(num); i++) {
                        if (num % i == 0) {
                            return false;
                        }
                    }
                    return true;
                };

                //获取质数的方法
                HashTable.prototype.getPrime = function (num) {
                    //7*2=14,+1=15,+1=16,+1=17(质数)
                    while (!this.isPrime(num)) {
                        num++;
                    }
                    console.log(num);
                    return num;
                };
            }
            var hashTable = new HashTable();
            hashTable.put('q', 1);
            hashTable.put('w', 1);
            hashTable.put('e', 1);
            hashTable.put('r', 1);
            hashTable.put('t', 1);
            hashTable.put('y', 1);
            hashTable.put('z', 1);
            hashTable.put('x', 1);
            hashTable.put('c', 1);
            hashTable.put('v', 1);
            hashTable.put('b', 1);
            hashTable.put('n', 1);
            hashTable.remove('q');
            console.log(hashTable.toString());
        </script>
    </body>
</html>
